// 实现数组的 交集、并集、差集、补集、拆分、去重，排列组合 n个元素取m个， 笛卡尔积算法
// -----------把下面用泛型改写merge2.go
package Shared

import "reflect"

//[只需要去掉对应相同的数]如s1:{11,11,11,11,5},s2:{11,11,11}
//返回 {11,5}
func SliceFirstUnique[T comparable](s1, s2 []T) []T {
	for _, v := range s2 {
		for k2, v2 := range s1 {
			if v == v2 {
				s1 = append(s1[:k2], s1[k2+1:]...)
				break
			}
		}
	}
	return s1
}

//插入元素
func SliceInsert[T comparable](s []T, val T, idx int) []T {
	rear := append([]T{}, s[idx:]...)
	s = append(s[0:idx], val)
	s = append(s, rear...)
	return s
}

// 删除元素
func SliceDel[T comparable](s []T, val T) []T {
	for i := 0; i < len(s); i++ {
		if s[i] != val {
			continue
		}
		s = append(s[:i], s[i+1:]...)
		i--
	}
	return s
}

//求交集
func SliceInter[T comparable](s1, s2 []T) []T {
	m := make(map[T]int)
	n := make([]T, 0)
	for _, v := range s1 {
		m[v]++
	}
	for _, v := range s2 {
		if times, _ := m[v]; times > 0 {
			n = append(n, v)
		}
	}
	return n
}

// 求并集
func SliceUnion[T comparable](s1, s2 []T) []T {
	m := make(map[T]int)
	for _, v := range s1 {
		m[v]++
	}
	for _, v := range s2 {

		if times, _ := m[v]; times == 0 {
			s1 = append(s1, v)
		}
	}
	return s1
}

// 求补集
func SliceComple[T comparable](s1, s2 []T) []T {
	m := make(map[T]int)
	for _, v := range s1 {
		m[v]++
	}
	for _, v := range s2 {
		m[v]++
	}
	n := make([]T, 0)
	for value, num := range m {
		if num == 1 {
			n = append(n, value)
		}
	}
	return n
}

// 求差集（s1-并集）
func SliceDiff[T comparable](s1, s2 []T) []T {
	m := make(map[T]int)
	n := make([]T, 0)
	inter := SliceInter(s1, s2)
	for _, v := range inter {
		m[v]++
	}
	for _, v := range s1 {
		if times, _ := m[v]; times == 0 {
			n = append(n, v)
		}
	}
	return n
}

// 求差集（s1-并集），delnum删除个数，之后重复也可保留
func SliceDiff22[T comparable](s1, s2 []T, delnum int) []T {
	m := make(map[T]int)
	n := make([]T, 0)
	inter := SliceInter(s1, s2)
	for _, v := range inter {
		m[v]++
	}
	count := 0 //计数器
	for _, v := range s1 {
		if count == delnum {
			break
		}
		if times, _ := m[v]; times == 0 {
			n = append(n, v)
			count++
		}

	}
	return n
}

// 拆分
func SliceSplit[T comparable](s []T, start, end int) (src, des []T) {
	if len(s) == 0 {
		return
	}
	if end > len(s) {
		end = len(s)
	}
	if start < 0 {
		start = 0
	}
	des = append(des, s[start:end]...)

	src = append(src, s[0:start]...)
	src = append(src, s[end:(len(s))]...)
	return
}

// 去重
func SliceUnique[T comparable](s [][]T) [][]T {
	result := make([][]T, 0)
	for i := 0; i < len(s); i++ {
		flag := false
		for j := i + 1; j < len(s); j++ {
			if reflect.DeepEqual(s[i], s[j]) {
				flag = true
				break
			}
		}
		if !flag {
			result = append(result, s[i])
		}
	}
	return result
}

// 排列组合 递归实现 n个元素中取m个元素的所有组合
// 例:{1,2,3} 取 2, 输出{{1,2}, {2,3}, {1,3}}
// 例:{1,2,3} 取 1, 输出{{1}, {2}, {3}}
func SliceCompute[T comparable](s []T, num int) [][]T {
	result := [][]T{}
	if len(s) == num {
		result = append(result, s)
	} else {
		makeCount := len(s) - num + 1
		for i := 0; i < makeCount; i++ {
			if num > 1 {
				split, _ := SliceSplit(s, 0, i+1)
				childCm := SliceCompute(split, num-1)
				for _, v := range childCm {
					v = SliceInsert(v, s[i], 0)
					result = append(result, v)
				}
			} else if num == 1 {
				result = append(result, []T{s[i]})
			}
		}
	}
	return SliceUnique(result)
}

// 排列组合 递归实现 n个元素中取最多m个元素的所有组合
// 例:{1,2,3} 取 2, 输出{{1}, {2}, {3}, {1,2}, {2,3}, {1,3}}
func SliceComputeAll[T comparable](s []T, num int) [][]T {
	result := [][]T{}
	for i := 1; i <= num; i++ {
		result = append(result, SliceCompute(s, i)...)
	}
	return result
}

// 笛卡尔积算法 多个数组的排列组合
// 例:{{1,2,3}, {4,5}}, 输出{{1,4}, {1,5}, {2,4}, {2,5}, {3,4}, {3,5}}
func _SlicePermutations[T comparable](ss [][]T, out *[][]T, idx int, idxes []int) {
	if idx < len(ss) {
		for i := 0; i < len(ss[idx]); i++ {
			idxes[idx] = i
			_SlicePermutations(ss, out, idx+1, idxes)
		}
	} else {
		cm := []T{}
		for i := 0; i < len(ss); i++ {
			cm = append(cm, ss[i][idxes[i]])
		}
		*out = append(*out, cm)
	}
}
func SlicePermutations[T comparable](ss [][]T) [][]T {
	result := [][]T{}
	idxes := make([]int, len(ss))
	_SlicePermutations(ss, &result, 0, idxes)
	return result
}
